package 动态规划;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author zhang lei
 * @Date 2021-11-12 21:30
 * @Description  最小路径和  https://leetcode-cn.com/problems/minimum-path-sum/
 */
public class Algo64 {

    private static Map<String, Integer> table= new HashMap<>();

    public static void main(String[] args) {
        int[][] arr = {{1,3,1},{1,5,1},{4,2,1}};
        int[][] arr2 = {{1,2,3},{4,5,6}};
        System.out.println(minPathSum(arr2));
    }

    /**
     * 思路：倒着递归遍历
     * (arr, i, j)
     * @param grid
     * @return
     */
    public static int minPathSum(int[][] grid) {
        return minPathDp(grid);
    }

    private static int minPathDp(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.length; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < grid[0].length; j++) {
            dp[0][j] =dp[0][j-1] +  grid[0][j];
        }


        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[grid.length-1][grid[0].length-1];
    }

    private static int minPathTable(int[][] grid, int i, int j) {
        if(i<0 || j<0) {
            return 0;
        }
        int n = grid[i][j];
        String key = i+","+j;
        if(table.get(key)!=null) {
            return table.get(key);
        }
        int result = -1;
        if(i == 0) {
            result =  n+ minPathTable(grid, i, j-1);
        }else if(j == 0) {
            result =  n + minPathTable(grid, i-1, j);
        }else {
            result = n + Math.min(minPathTable(grid, i - 1, j), minPathTable(grid, i, j - 1));
        }
        table.put(key, result);
        return result;
    }
}
